import random
import time
import math

class CombinationGenerator:
    """组合问题测试数据生成器"""
    
    @staticmethod
    def get_basic_cases():
        """基础测试用例"""
        return [
            # LeetCode 官方示例
            (4, 2, "LeetCode示例1 (n=4, k=2)"),
            (1, 1, "LeetCode示例2 (n=1, k=1)"),
            
            # 边界情况
            (1, 1, "最小情况"),
            (5, 1, "选1个"),
            (5, 5, "选全部"),
            (6, 3, "选一半"),
            
            # 常见情况
            (3, 2, "3选2"),
            (5, 2, "5选2"),
            (6, 4, "6选4"),
            (7, 3, "7选3"),
        ]
    
    @staticmethod
    def get_edge_cases():
        """边界情况测试用例"""
        return [
            (2, 1, "最小n选1"),
            (2, 2, "最小n选全部"),
            (10, 1, "大n选1"),
            (10, 10, "大n选全部"),
            (8, 4, "中间值"),
        ]
    
    @staticmethod
    def get_performance_cases():
        """性能测试用例"""
        return [
            (10, 5, "10选5 (最大组合数)"),
            (12, 6, "12选6"),
            (15, 7, "15选7"),
            (13, 3, "13选3"),
            (14, 4, "14选4"),
            (16, 2, "16选2"),
            (18, 9, "18选9"),
        ]
    
    @staticmethod
    def generate_random_cases(count=5):
        """生成随机测试用例"""
        cases = []
        for i in range(count):
            n = random.randint(5, 15)
            k = random.randint(1, n)
            cases.append((n, k, f"随机测试{i+1} (n={n}, k={k})"))
        return cases
    
    @staticmethod
    def calculate_expected_count(n, k):
        """计算期望的组合数量 C(n,k)"""
        if k > n or k < 0:
            return 0
        if k == 0 or k == n:
            return 1
        
        # 使用 C(n,k) = C(n,n-k) 优化计算
        k = min(k, n - k)
        
        result = 1
        for i in range(k):
            result = result * (n - i) // (i + 1)
        
        return result
    
    @staticmethod
    def validate_combinations(combinations, n, k):
        """验证组合结果的正确性"""
        errors = []
        
        # 检查组合数量
        expected_count = CombinationGenerator.calculate_expected_count(n, k)
        if len(combinations) != expected_count:
            errors.append(f"组合数量错误: 期望{expected_count}, 实际{len(combinations)}")
        
        # 检查每个组合
        for i, combo in enumerate(combinations):
            # 检查长度
            if len(combo) != k:
                errors.append(f"组合{i}长度错误: 期望{k}, 实际{len(combo)}")
            
            # 检查元素范围
            for num in combo:
                if num < 1 or num > n:
                    errors.append(f"组合{i}包含超出范围的元素: {num}")
            
            # 检查是否有序
            if combo != sorted(combo):
                errors.append(f"组合{i}不是有序的: {combo}")
            
            # 检查是否有重复元素
            if len(combo) != len(set(combo)):
                errors.append(f"组合{i}包含重复元素: {combo}")
        
        # 检查是否有重复组合
        unique_combos = set(tuple(combo) for combo in combinations)
        if len(unique_combos) != len(combinations):
            errors.append("存在重复的组合")
        
        return errors


class TestRunner:
    """测试运行器"""
    
    def __init__(self, solution_class):
        self.solution = solution_class()
        self.generator = CombinationGenerator()
        self.passed = 0
        self.total = 0
        self.failed_cases = []
    
    def run_test(self, n, k, description=""):
        """运行单个测试"""
        self.total += 1
        
        try:
            # 执行算法
            start_time = time.time()
            result = self.solution.combine(n, k)
            end_time = time.time()
            
            # 计算期望结果数量
            expected_count = self.generator.calculate_expected_count(n, k)
            
            # 验证结果
            errors = self.generator.validate_combinations(result, n, k)
            
            if not errors:
                self.passed += 1
                status = "✓ PASS"
            else:
                status = "✗ FAIL"
                self.failed_cases.append((description, n, k, errors))
            
            print(f"测试 {self.total:2d}: {description}")
            print(f"         参数: n={n}, k={k}")
            print(f"         组合数: {len(result)} (期望: {expected_count})")
            print(f"         状态: {status}")
            print(f"         耗时: {(end_time - start_time)*1000:.2f}ms")
            
            # 显示部分结果
            if len(result) <= 20:
                print(f"         结果: {result}")
            else:
                print(f"         结果: {result[:5]} ... {result[-5:]} (共{len(result)}个)")
            
            if errors:
                print(f"         错误: {'; '.join(errors[:3])}")
            
            print("-" * 60)
            
        except Exception as e:
            print(f"测试 {self.total}: {description} - ERROR: {str(e)}")
            self.failed_cases.append((description, n, k, [f"异常: {str(e)}"]))
            print("-" * 60)
    
    def run_all_tests(self):
        """运行所有测试"""
        print("=" * 60)
        print(" 组合问题测试套件")
        print("=" * 60)
        
        # 1. 基础测试
        print("\n【基础测试用例】")
        for n, k, desc in self.generator.get_basic_cases():
            self.run_test(n, k, desc)
        
        # 2. 边界测试
        print("\n【边界情况测试】")
        for n, k, desc in self.generator.get_edge_cases():
            self.run_test(n, k, desc)
        
        # 3. 随机测试
        print("\n【随机测试】")
        for n, k, desc in self.generator.generate_random_cases(5):
            self.run_test(n, k, desc)
        
        # 4. 性能测试
        print("\n【性能测试】")
        for n, k, desc in self.generator.get_performance_cases():
            self.run_test(n, k, desc)
        
        # 测试总结
        self.print_summary()
    
    def print_summary(self):
        """打印测试总结"""
        print("\n" + "=" * 60)
        print(" 测试总结")
        print("=" * 60)
        print(f"总测试数: {self.total}")
        print(f"通过测试: {self.passed}")
        print(f"失败测试: {len(self.failed_cases)}")
        print(f"通过率: {(self.passed/self.total*100):.1f}%")
        
        if self.failed_cases:
            print("\n失败的测试用例:")
            for desc, n, k, errors in self.failed_cases:
                print(f"  - {desc} (n={n}, k={k})")
                for error in errors[:3]:  # 只显示前3个错误
                    print(f"    {error}")
        else:
            print("\n🎉 所有测试用例均通过!")


# Solution类 (从原代码复制)
class Solution(object):
    def combine(self, n, k):
        result = []
        
        def backtrack(start, path):
            if len(path) == k:
                result.append(path[:])
                return
            
            for i in range(start, n + 1):
                path.append(i)
                backtrack(i + 1, path)
                path.pop()
        
        backtrack(1, [])
        return result


# 运行测试
if __name__ == "__main__":
    runner = TestRunner(Solution)
    runner.run_all_tests()
